/*
 * @Author: liusheng
 * @Date: 2022-06-26 16:06:36
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 16:06:38
 * @Description: 剑指 Offer II 083. 没有重复元素集合的全排列
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 083. 没有重复元素集合的全排列
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

 

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]
 

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
 

注意：本题与主站 46 题相同：https://leetcode-cn.com/problems/permutations/ 

通过次数14,794提交次数17,298
 */

#include "header.h"
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        permute(nums,0,result);
        return result;
    }
private:
    void permute(vector<int>& nums,int curIndex,vector<vector<int>> &result)
    {
        if (curIndex == nums.size())
        {
            result.push_back(nums);
            return;
        }
        
        for (int i = curIndex; i < nums.size(); ++i)
        {
            swap(nums[i],nums[curIndex]);
            permute(nums,curIndex + 1,result);
            //backtrace
            swap(nums[i],nums[curIndex]);
        }
    }
};